package binarytree

import "fmt"

//定义树中的数据类型
type BElem int

type BNode struct {
	//数据
	Data BElem
	//左节点和右节点
	LeftChild, RightChild *BNode
}

//定义一个别名作为树
type BTree BNode

//CreateTree 创建初始化一个树
func CreateTree(t *BTree) {
	t.Data = 1
	t.LeftChild = new(BNode)
	t.RightChild = new(BNode)
	t.LeftChild.Data = 2
	t.RightChild.Data = 3
	t.LeftChild.LeftChild = new(BNode)
	t.LeftChild.RightChild = new(BNode)
	t.LeftChild.LeftChild.Data = 4
	t.LeftChild.RightChild.Data = 5
	t.LeftChild.LeftChild.LeftChild = nil
	t.LeftChild.LeftChild.RightChild = nil
	t.LeftChild.RightChild.LeftChild = nil
	t.LeftChild.RightChild.RightChild = nil
	t.RightChild.LeftChild = new(BNode)
	t.RightChild.RightChild = new(BNode)
	t.RightChild.LeftChild.Data = 6
	t.RightChild.RightChild.Data = 7
	t.RightChild.LeftChild.LeftChild = nil
	t.RightChild.RightChild.LeftChild = nil
	t.RightChild.LeftChild.RightChild = nil
	t.RightChild.RightChild.RightChild = nil
}

//DisplayElem 打印元素
func DisplayElem(b *BNode) {
	fmt.Printf("%d \n", b.Data)
}

//PreOrderTraverse 先序遍历
func PreOrderTraverse(t *BTree) {
	if t != nil {
		DisplayElem((*BNode)(t))
		//左子树
		PreOrderTraverse((*BTree)(t.LeftChild))
		//右子树
		PreOrderTraverse((*BTree)(t.RightChild))
	}
}

//弹栈
func pop(top *int) {
	if *top == -1 {
		return
	}
	*top--
}

//入栈
func push(a []*BNode, elem *BNode, top *int) {
	*top++
	a[*top] = elem
}

//获取栈顶元素
func getTop(a []*BNode, top *int) *BNode {
	return a[*top]
}

//PreOrderTraverseStack 先序遍历(栈实现)
func PreOrderTraverseStack(t *BTree) {
	var a []*BNode = make([]*BNode, 20)
	var p *BNode
	var top int
	//根节点入栈
	push(a, (*BNode)(t), &top)
	for top != -1 {
		p = getTop(a, &top)
		pop(&top)
		for p != nil {
			DisplayElem(p)
			if (*p).RightChild != nil {
				push(a, (*p).RightChild, &top)
			}
			p = (*p).LeftChild
		}
	}
}
